Big M

Big M — метод решения задач линейного программирования с использованием симплексного алгоритма. Позволяет распространить симплексный алгоритм на задачи, которые содержат ограничения «больше, чем». Такое распространение осуществляется за счёт того, что связи ассоциируются с большими по величине отрицательными постоянными, которые не были бы частью какого-либо оптимального решения, если бы оно существовало.

Алгоритм

Симплекс-метод является оригинальным и до сих пор одним из наиболее широко используемых методов решения задач линейной максимизации. Однако для его применения начало координат (все переменные равны 0) должно быть допустимой точкой. Это условие выполняется только тогда, когда все связи (кроме неотрицательности) меньше связей типа «меньше чем» и с положительной константой в правой части. Метод вводит избыточные и искусственные переменные для преобразования всех неравенств к этому виду; название метода обусловлено наличием большого числа искусственных переменных, обозначаемых $M$.

Шаги в алгоритме следующие:

• умножить выражения для связей в виде неравенства так, чтобы убедиться, что правая часть положительна;
• если ставится задача минимизации, то её надо преобразовать в задачу максимизации за счёт умножения целевой функции на −1;
• для любых ограничений, превышающих допустимые, введите избыточные переменные $s_{i}$ и искусственные переменные $\varphi _{i}$ф_i так, как это показано ниже^{[уточнить]};
• выбрать большое положительное значение $M$ и введите в целевую функцию формы соответствующее слагаемые вида $-M$, умноженного на искусственные переменные;
• для ограничений вида «меньше или равно» вводятся переменные рассогласования $s_{i}$s_i таким образом, чтобы все ограничения обратились в равенство;
• полученная задача решается обычным симплексным методом.

Например, ограничение $x+y\leqslant 100$ принимает вид $x+y+s_{1}=100$, в то время как ограничение $x+y\geqslant 100$ записывается как $x+y-s_{1}+a_{1}=100$. Должно быть показано, что искусственные переменные равны 0. Функция, подлежащая максимизации, переписывается так, чтобы включить в неё сумму всех искусственных переменных. Затем применяются сокращения строк для получения окончательного решения.

Значение $M$ должно быть выбрано достаточно большим, чтобы искусственная переменная не была частью какого-либо осуществимого решения.

Для достаточно большого $M$ оптимальное решение содержит любые искусственные переменные в базисе (то есть положительные значения) тогда и только тогда, когда задача не имеет решения.

Альтернативные применения

При использовании в целевой функции метод Big M применяется для задач линейной оптимизации, в которых нарушения связи или нескольких связей обусловлено наличием большой положительной штрафной постоянной $M$.

При использовании в самих связях, Big M может быть применён для обеспечения равенства переменных только тогда, когда определённая двоичная переменная принимает одно значение, но оставляет переменные «открытыми», если двоичная переменная принимает противоположное значение. Один из примеров этого заключается в следующем: для достаточно больших двоичных переменных $M$ и $z$ (0 или 1) связи:

$x-y\leqslant Mz$

$x-y\geqslant -Mz$

обеспечивают тот факт, что если $z=0$, то $x=y$. В противном случае, когда выполняется условие если $z=1$, то имеет место неравенство $-M\leqslant x-y\leqslant M$, указывающее на то, что переменные x и y могут иметь любые значения до тех пор, пока абсолютное значение их разности ограничено величиной $M$ (следовательно, необходимо, чтобы $M$ было «достаточно большим»).

См. также

• Двухфазный метод (линейное программирование) — метод предлагающий ещё один подход к решению задач с ограничениями типа нестрогих неравенств.
• Условия Каруша — Куна — Таккера — условия, которые применяются к задачам нелинейной оптимизации с ограничениями типа неравенств.

Литература

• Griva, Igor. Linear and Nonlinear Optimization / Igor Griva, Stephan G. Nash, Ariela Sofer. — 2nd. — Society for Industrial Mathematics, 26 March 2009. — ISBN 978-0-89871-661-0.

Ссылки

• Simplex — Big M Method, Lynn Killen, Dublin City University.
• The Big M Method, businessmanagementcourses.org
• The Big M Method, Mark Hutchinson
• The Big-M Method with the Numerical Infinite M, a recently introduced parameterless variant
• A Three-phase Simplex Method For Infeasible And Unbounded Linear Programming Problems, Big M method for M=1